package com.zjsru.leetcode75.level1;

/**
 * @Author: cookLee
 * @Date: 2023-12-25
 * 编辑距离
 */
public class MinDistance {

    /**
     * 主
     * \
     * 输入：word1 = "horse", word2 = "ros"
     * 输出：3
     * 解释：
     * horse -> rorse (将 'h' 替换为 'r')
     * rorse -> rose (删除 'r')
     * rose -> ros (删除 'e')
     * \
     * 输入：word1 = "intention", word2 = "execution"
     * 输出：5
     * 解释：
     * intention -> inention (删除 't')
     * inention -> enention (将 'i' 替换为 'e')
     * enention -> exention (将 'n' 替换为 'x')
     * exention -> exection (将 'n' 替换为 'c')
     * exection -> execution (插入 'u')
     * \
     * @param args args
     */
    public static void main(String[] args) {
        MinDistance minDistance = new MinDistance();
        String word1 = "horse";
        String word2= "ros";
        System.out.println(minDistance.minDistance(word1, word2));
    }


    /**
     * 最小距离
     * 动态规划
     * @param word1 word1
     * @param word2 word2
     * @return int
     */
    public int minDistance(String word1, String word2) {
        int len1 = word1.length();
        int len2 = word2.length();
        int[][] dp = new int[len1 + 1][len2 + 1];
        //第一列
        for (int i = 1; i <= len1; i++) {
            dp[i][0] = dp[i - 1][0] + 1;
        }
        //第一行
        for (int i = 1; i <= len2; i++) {
            dp[0][i] = dp[0][i - 1] + 1;
        }
        //dp[i-1][j-1] 表示替换操作，dp[i-1][j] 表示删除操作，dp[i][j-1] 表示插入操作。
        for (int i = 1; i <= len1; i++) {
            for (int j = 1; j <= len2; j++) {
                char c1 = word1.charAt(i - 1);
                char c2 = word2.charAt(j - 1);
                if (c1 == c2) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    //删除 (dp[i-1][j])、插入 (dp[i][j-1]) 和替换 (dp[i-1][j-1])。选择其中操作的最小成本，并加1
                    dp[i][j] = Math.min(dp[i- 1][j], Math.min(dp[i - 1][j - 1], dp[i][j - 1])) + 1;
                }
            }
        }
        return dp[len1][len2];
    }


}
